/*
 * @lc app=leetcode.cn id=128 lang=typescript
 *
 * [128] 最长连续序列
 */

// @lc code=start

class UnionFind {
  parent: number[];
  size: number[];
  count: number;
  constructor(n: number = 0) {
    this.parent = new Array(n).fill(0).map((_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n;
  }
  find(x: number): number {
    return (this.parent[x] = this.parent[x] === x ? x : this.find(this.parent[x]));
  }
  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.size[ry] += this.size[rx];
    this.parent[rx] = ry;
    this.count--;
  }
}

function longestConsecutive(nums: number[]): number {
  const size = nums.length;
  const unionFind = new UnionFind(size);
  const map = new Map();
  // 将num的下标和num+1或num-1的下标连通
  for (let i = 0; i < size; i++) {
    const num = nums[i];
    // 如果出现过，就跳过，避免重复连通
    if (map.has(num)) continue;
    if (map.has(num - 1)) {
      unionFind.union(i, map.get(num - 1));
    }
    if (map.has(num + 1)) {
      unionFind.union(i, map.get(num + 1));
    }
    map.set(num, i);
  }

  let result = 0;
  // 统计并查集中最大的集合的长度
  for (let i = 0; i < size; i++) {
    // 找到集合的根
    if (unionFind.find(i) === i) {
      result = Math.max(result, unionFind.size[i]);
    }
  }

  return result;
}
// @lc code=end
